a once
#include<vector>
#include<iostream>
#include<time.h>
#include<windows.h>
using std::cout;
using std::endl;


inline static void* SystemAlloc(size_t kpage)//直接去堆上申请空间，不再使用malloc内存池
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
	// linux下brk mmap等
#endif

	if (ptr == nullptr)
		throw std::bad_alloc();

	return ptr;
}


template<class T>
class FixedPool
{
private:
	char* _memory=nullptr;//指向定长内存的指针
	size_t _remainmemory=0;//剩余定长内存的字节个数
	void* _freelist = nullptr;//指向使用完的内存的指针
public:

	T* New()//申请一个对象空间
	{
		T*obj = nullptr;
		if (_freelist)//先把还回来的内存使用
		{
			void* next = *(void**)_freelist;//取到空闲块的下一个位置
			obj = (T*)_freelist;
			_freelist = next;
		}
		else
		{
			if (_remainmemory < sizeof(T))//剩余的内存不够一个对象的时候重新开空间
			{
				//_memory = (char*)malloc(128 * 1024);

				_remainmemory = 128 * 1024;
				_memory = (char*)SystemAlloc(_remainmemory>>13);//参数是页的个数
				if (_memory == nullptr)
				{
					throw std:: bad_alloc();
				}
			}
			obj = (T*)_memory;
			size_t objsize = sizeof(T)>sizeof(void*) ? sizeof(T) : sizeof(void*);//解决申请的空间在释放的时候不能存储下一个位置地址的问题
			_memory += objsize;//就算你类型的大小不能存储一个指针的大小，我也强制给你多开空间让你能够存储指针
			_remainmemory -= objsize;
		}
		new(obj)T;//定位new，初始化对象
		return obj;
	}

	void Delete(T* obj)//不需要像以前一样free释放内存，因为内存池上的内存是不需要释放的，只要做到理论上的free即可
	{
		//使用头插的方式串接空间
		obj->~T();//清楚对象内部的空间，如string，vector
		*(void**)obj = _freelist;//使用二级指针的目的是为了解决32位和64位下地址大小不一样的问题
		_freelist = obj;
	}

};

struct TreeNode
{
	int _val;
	TreeNode* _left;
	TreeNode* _right;

	TreeNode()
		:_val(0)
		, _left(nullptr)
		, _right(nullptr)
	{}
};

FixedPool<TreeNode> TNPool;


void TestObjectPool()
{
	// 申请释放的轮次
	const size_t Rounds = 5;

	// 每轮申请释放多少次
	const size_t N = 100000;

	std::vector<TreeNode*> v1;
	v1.reserve(N);

	size_t begin1 = clock();
	for (size_t j = 0; j < Rounds; ++j)
	{
		for (int i = 0; i < N; ++i)
		{
			v1.push_back(new TreeNode);
		}
		for (int i = 0; i < N; ++i)
		{
			delete v1[i];
		}
		v1.clear();
	}

	size_t end1 = clock();

	std::vector<TreeNode*> v2;
	v2.reserve(N);

	//ObjectPool<TreeNode> TNPool;
	size_t begin2 = clock();
	for (size_t j = 0; j < Rounds; ++j)
	{
		for (int i = 0; i < N; ++i)
		{
			v2.push_back(TNPool.New());
		}
		for (int i = 0; i < N; ++i)
		{
			TNPool.Delete(v2[i]);
		}
		v2.clear();
	}
	size_t end2 = clock();

	cout << "new cost time:" << end1 - begin1 << endl;
	cout << "object pool cost time:" << end2 - begin2 << endl;
}
